

//循环队列---解决数组队列出队性能不高的问题
/*
    通过维护front(指向队首，第一个出队的元素)和tail(指向队尾，每次元素进队的位置)

    每次出队，出队front的元素后让front++ 让front指向下一个队首元素
    这样就不用像底层数组一样所有元素向前移动，但数组index=front的位置前面会出现没利用的空间

    每次入队，在tail的地方插入元素后，tail++成为下一个元素插入的位置
    当(tail+1%capacity)==0时，代表到最后了，此时tail需要移动到index=0的位置，把因为front导致的没利用的空间利用起来

    front==tail 队列空

     有意识的浪费一个空间使得
    (tail+1) % capacity==front 队列满

    如果不有意识的浪费一个空间那么  front==tail 代表队列空/满
    这里我们区别开来，所以使用浪费一个空间的形式

*/
public class LoopQueue<E> implements Queue<E>{

    //这里使用以前自己写的动态数组不方便，要修改很麻烦，所以这里我们重新从底层写起，重新维护一个数组实现。

    private E[] data;
    private int front,tail;
    private int size ;  //其实可以通过tail代替这个size

    public LoopQueue(int capacity){
        //因为需要浪费一个空间
        data = (E[]) new Object[capacity+1];
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        //因为有一个空间被我们有意识的浪费。
        return  data.length-1;
    }

    @Override
    public boolean isEmpty(){
        return front==tail;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    //进队
    public void enqueue(E e){
        //如果队列满了就要扩容
        if((tail+1) % data.length==front)
            resize(getCapacity()*2);

        data[tail]=e;
        tail=(tail+1)%data.length;  //维护tail,下次元素进队的位置
        size++; //维护素组长度
    }

    @Override
    //出队
    public E dequeue(){
        //如果队列是空的不能出队
        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        E res=data[front];
        data[front]=null;   //这个元素已经出对了用户也访问不到，置为null让他被java垃圾回收机制等待回收
        front =(front+1)%data.length; //维护front，下个出队位置
        size--; //维护数组长度
        //如果太多空间没使用到就缩容
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);
        return res;
    }

    @Override
    //查看队首元素
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    public void resize(int newCapacity){
        //因为会有意识的浪费一个空间，所以开辟的空间要+1
        E[] newData = (E[])new Object[newCapacity+1];
        for(int i=0;i<size;i++){
            //front不一定在0的位置,且i+front可能会大于size，让他循环到前面
            newData[i]=data[(i+front)%data.length];
        }
        front=0;    //newData是从0开始所以front是0
        tail=size;     //newData是从0开始的所以tail就是size
        data=newData;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        //队列元素从front开始，只要front!=tail代表里面不是空，就可以遍历，里面不是每次+1可能越界，而是循环。
        for(int i = front ; i != tail ; i = (i + 1) % data.length){
            res.append(data[i]);
            if((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args){

        LoopQueue<Integer> queue = new LoopQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }


}
